//给你两个数组，arr1 和 arr2， 
//
// 
// arr2 中的元素各不相同 
// arr2 中的每个元素都出现在 arr1 中 
// 
//
// 对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末
//尾。 
//
// 
//
// 示例： 
//
// 输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
//输出：[2,2,2,1,4,3,3,9,6,7,19]
// 
//
// 
//
// 提示： 
//
// 
// arr1.length, arr2.length <= 1000 
// 0 <= arr1[i], arr2[i] <= 1000 
// arr2 中的元素 arr2[i] 各不相同 
// arr2 中的每个元素 arr2[i] 都出现在 arr1 中 
// 
// Related Topics 排序 数组

package leetcode.editor.cn;

import java.util.ArrayList;

public class RelativeSortArray {
    public static void main(String[] args) {
        Solution solution = new RelativeSortArray().new Solution();
        int[] ints = solution.relativeSortArray(new int[]{2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19},
                new int[]{2, 1, 4, 3, 9, 6});
        for (int anInt : ints) {
            System.out.println(anInt);
        }
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        /**
         * 因为，数字的范围，是0-1000，所以，我们申请一个数组，一共1001这么大
         * 下标就对应，每个数字，比如，数字8，就存储在arr[8]里面，
         * 我们这个数组，主要用来存放，该数字在数组中出现的次数。
         *
         * 因为数组arr1，arr2的长度小于等于1000，所以，极端情况下，即，传入的arr1里数字全部相同
         * 假设都是2，
         * 那么count[2] = 1000;
         */
        int[] count = new int[1001];

        for (int i = 0; i < arr1.length; i++) {
            int a1 = arr1[i];
            /**
             * 出现1次
             */
            count[a1] += 1;
        }

        for (int i : arr2) {
            count[i] += 1001;
        }

        /**
         * 目前为止，如果一个数字，在两个数组都出现了的，那么，count数，是大于1001的
         */
        int tmp = 0;
        for (int a2 : arr2) {
            int totalCount = count[a2];
            while (totalCount > 1001) {
                arr1[tmp++] = a2;
                totalCount--;
            }
        }

        for (int i = 0; i < count.length; i++) {
            int counter = count[i];

            /**
             * 没在数组2中出现的元素，可能在1里多次出现，那么，此时counter[7]，假设7是没在arr2出现的
             * 在arr1出现了2次，那么，counter[7] = 2
             */
            while (counter > 0 && counter < 1000) {
                arr1[tmp++] = i;
                counter--;
            }
        }

        return arr1;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}